package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-16
 */

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 *
 * 注意：
 *
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 */
public class leetcode76 {
    public String minWindow(String s, String t) {
        if (s==null || s.length()==0 || t==null || t.length()==0) return "";
        //每个char字符对应一个位置
        int[] need = new int[128];
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++; //t.charAt(i) 返回一个字符
        }
        //l,r维持窗口，start记录最小窗口的开始位置
        int l=0, r=0, res = Integer.MAX_VALUE, count=t.length(), start=0;
        while (r<s.length()){
            char c = s.charAt(r);
            if (need[c]>0) count--;
            need[c]--;

            if (count==0){
                //如果l往右移也能保持窗口包含所有字符，则移动
                while (l<r && need[s.charAt(l)]<0){
                    need[s.charAt(l)]++;
                    l++;
                }
                if (r-l+1 < res){
                    res = r-l+1;
                    start = l;
                }
                need[s.charAt(l)]++;
                l++;
                count++;
            }
            r++;
        }
        return res == Integer.MAX_VALUE?"":s.substring(start,start+res);
    }
}
